#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define MAX_PROJECTS 6
#define MAX_ATHLETES 5

char projectLabels[MAX_PROJECTS] = {'A', 'B', 'C', 'D', 'E', 'F'};
int graph[MAX_PROJECTS][MAX_PROJECTS];
int time_slots[MAX_PROJECTS];
int num_projects = MAX_PROJECTS;
int found_schedules = 0;

// 初始化邻接矩阵
void initialize_graph() {
	for (int i = 0; i < num_projects; i++) {
		for (int j = 0; j < num_projects; j++) {
			graph[i][j] = 0;
		}
	}
}

// 构建冲突图
void build_conflict_graph(int num_athletes, int athlete_projects[][MAX_PROJECTS], int num_projects_per_athlete[]) {
	initialize_graph();
	
	for (int k = 0; k < num_athletes; k++) {
		for (int i = 0; i < num_projects_per_athlete[k]; i++) {
			for (int j = i + 1; j < num_projects_per_athlete[k]; j++) {
				int p1 = athlete_projects[k][i];
				int p2 = athlete_projects[k][j];
				graph[p1][p2] = 1;
				graph[p2][p1] = 1;
			}
		}
	}
}

// 检查项目在时间段中的可用性
int is_available(int project, int time_slot) {
	for (int i = 0; i < num_projects; i++) {
		if (graph[project][i] == 1 && time_slots[i] == time_slot) {
			return 0; // 冲突
		}
	}
	return 1; // 可用
}

// 尝试为所有项目分配时间段
void assign_time_slots(int project) {
	if (project == num_projects) { // 所有项目已经分配
		printf("运动会计划 %d:\n", ++found_schedules);
		for (int t = 0; t < num_projects; t++) {
			printf("时间段 %d: ", t + 1);
			for (int i = 0; i < num_projects; i++) {
				if (time_slots[i] == t) {
					printf("项目 %c ", projectLabels[i]);
				}
			}
			printf("\n");
		}
		Sleep(2000);
		printf("\n");
		return; 
	}
	
	for (int time_slot = 0; time_slot < num_projects; time_slot++) {
		if (is_available(project, time_slot)) {
			time_slots[project] = time_slot; // 分配时间段
			
			assign_time_slots(project + 1); // 递归分配下一个项目
			
			// 回溯
			time_slots[project] = -1; 
		}
	}
}

int main() {
	int num_athletes = MAX_ATHLETES;
	int athlete_projects[MAX_ATHLETES][MAX_PROJECTS] = {
		{0, 1, 4}, // 运动员 1：项目 A, B, E
		{2, 3},    // 运动员 2：项目 C, D
		{2, 4, 5}, // 运动员 3：项目 C, E, F
		{3, 5, 0}, // 运动员 4：项目 D, F, A
		{1, 5}     // 运动员 5：项目 B, F
	};
	int num_projects_per_athlete[MAX_ATHLETES] = {3, 2, 3, 3, 2}; 
	
	build_conflict_graph(num_athletes, athlete_projects, num_projects_per_athlete);
	
	// 初始化时间段数组
	for (int i = 0; i < num_projects; i++) {
		time_slots[i] = -1; // -1 表示未分配时间段
	}
	
	assign_time_slots(0); // 从第一个项目开始分配时间段
	
	if (found_schedules == 0) {
		printf("无法找到有效的调度方案。\n");
	}
	
	return 0;
}

